use std::collections::{BTreeMap, VecDeque};

// 游戏中的人物块数量
const BLOCK_COUNT: u8 = 10;
// 人物块加上空格块的数量
const BLOCK_AND_BLACK: usize = BLOCK_COUNT as usize + 2;
// 块位数
const BLOCK_BITS: usize = 2;
// 块掩码
const BLOCK_MASK: u32 = (1 << BLOCK_BITS) - 1;
// 每个位置占用的bit数
const POSITION_BITS: u8 = 5;
// 获取一个位置的掩码
// 棋盘宽度
const BOARD_WIDTH: u8 = 4;
// 棋盘高度
const BOARD_HIGHT: u8 = 5;
// 棋盘上格子数
const CELL_COUNT: u8 = BOARD_HIGHT * BOARD_WIDTH;

#[derive(Default, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
struct Piece {
    w: u8,
    h: u8,
    y: u8,
    x: u8,
}

#[derive(Copy, Clone, Debug)]
pub struct State {
    piece: [Piece; BLOCK_AND_BLACK],
}

#[derive(Copy, Clone, Debug)]
pub struct MoveItem {
    from: u8,
    to: u8,
}

#[derive(Copy, Clone, Debug)]
enum Resource {
    None,
    One(u8),
    Two(u8, u8),
    BossMove([u8; 6]),
}
impl Resource {
    fn h(c: u8, pos: u8) -> Resource {
        if c == 1 {
            Resource::One(pos)
        } else {
            Resource::Two(pos, pos + 1)
        }
    }
    fn v(c: u8, pos: u8) -> Resource {
        if c == 1 {
            Resource::One(pos)
        } else {
            Resource::Two(pos, pos + BOARD_WIDTH)
        }
    }
}

impl MoveItem {
    fn from_change(from: u8, to: u8) -> MoveItem {
        MoveItem { from, to }
    }
    fn new() -> MoveItem {
        MoveItem {
            from: CELL_COUNT as u8,
            to: CELL_COUNT as u8,
        }
    }
}

#[derive(Copy, Clone, Debug)]
pub struct Move {
    item: [MoveItem; 3],
}

impl Move {
    fn from_change(p1: u8, p2: u8) -> Move {
        Move {
            item: [
                MoveItem::from_change(p1, p2),
                MoveItem::from_change(p2, p1),
                MoveItem::new(),
            ],
        }
    }
    fn a2b_b2c(a: u8, b: u8, c: u8) -> Move {
        Move {
            item: [
                MoveItem::from_change(a, b),
                MoveItem::from_change(b, c),
                MoveItem::new(),
            ],
        }
    }
    fn change_ab_c2d(a: u8, b: u8, c: u8, d: u8) -> Move {
        Move {
            item: [
                MoveItem::from_change(a, b),
                MoveItem::from_change(b, a),
                MoveItem::from_change(c, d),
            ],
        }
    }
    fn from_6u8(x: [u8; 6]) -> Move {
        Move {
            item: [
                MoveItem::from_change(x[0], x[1]),
                MoveItem::from_change(x[2], x[3]),
                MoveItem::from_change(x[4], x[5]),
            ],
        }
    }
}

impl State {
    pub fn from_u32(zip: u32) -> State {
        let mut piece: [Piece; BLOCK_AND_BLACK] = Default::default();
        let o_p = u32_to_pieces(zip);
        for i in 0..BLOCK_AND_BLACK {
            piece[i] = o_p[i];
        }
        State { piece }
    }
    pub fn from_u64(zip: u64) -> State {
        let mut piece: [Piece; BLOCK_AND_BLACK] = Default::default();
        let o_p = u32_to_pieces(zip as u32);
        for i in 0..BLOCK_AND_BLACK {
            piece[i] = o_p[i];
        }
        State { piece }
    }
    pub fn zip(&self) -> u32 {
        let mut zip: u32 = 0;
        let mut idx = [0_usize; BLOCK_AND_BLACK];
        (0..BLOCK_AND_BLACK).for_each(|i| idx[i] = i);
        idx.sort_by(|a, b| self.piece[*a].one_dim().cmp(&self.piece[*b].one_dim()));
        idx.iter()
            .enumerate()
            .filter(|(_, &i)| i > 9)
            .for_each(|(i, _)| zip = (zip << 4) | i as u32);
        (0..BLOCK_AND_BLACK)
            .rev()
            .for_each(|i| zip = (zip << BLOCK_BITS) | self.piece[idx[i]].zip());
        zip
    }
    pub fn zip64(&self) -> u64 {
        let mut ps = self.piece.clone();
        ps[0..10].sort();
        let mut zip: u64 = 0;
        for i in [8, 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11].into_iter().rev() {
            zip = (zip << POSITION_BITS) | ps[i].one_dim() as u64;
        }
        zip
    }
    fn s1(&self) -> Piece {
        self.piece[10]
    }
    fn s2(&self) -> Piece {
        self.piece[11]
    }
    pub fn apply_move(&mut self, m: Move) -> bool {
        let state = self.clone();
        let x = m
            .item
            .map(|x| {
                (
                    x,
                    if x.from < CELL_COUNT {
                        state.piece.iter().position(|&y| y.one_dim() == x.from)
                    } else {
                        None
                    },
                )
            })
            .map(|x| {
                if let Some(i) = x.1 {
                    self.piece[i] = state.piece[i].move_to(x.0.to);
                    self.piece[i].is_over()
                } else {
                    false
                }
            });
        x.iter().any(|&x| x)
    }
    fn horizontal_space(&self) -> bool {
        self.s1().y == self.s2().y && self.s1().x + 1 == self.s2().x
    }
    fn vertical_space(&self) -> bool {
        self.s1().x == self.s2().x && self.s1().y + 1 == self.s2().y
    }
    pub fn next_steps(&self) -> Vec<Move> {
        let mut moves: Vec<Move> = Vec::new();
        for i in 0..BLOCK_COUNT {
            moves.extend(self.find_move(i));
        }
        moves
    }
    pub fn test_move(&self, x: u32)  -> Result<Vec<u8>, ()> {
        let piece = |ps: &[Piece; BLOCK_AND_BLACK]| (0..10).into_iter().map(|i|ps[i].one_dim()).collect::<Vec<u8>>().try_into().unwrap();
        let space = |ps: &[Piece; BLOCK_AND_BLACK]| [ps[10].one_dim(), ps[11].one_dim()];

        let state = State::from_u32(x);
            let source: [u8; 10] = piece(&self.piece);
            let target: [u8; 10] = piece(&state.piece);
            let s_s = space(&self.piece);
            let t_s = space(&state.piece);
            let sub = |a: [u8; 10], b: [u8; 10]| a.into_iter().filter(|&x| !b.contains(&x)).collect::<Vec<u8>>();
            let xx = sub(source.clone(), target.clone()).into_iter().zip(sub(target, source));
            let sub = |a: [u8; 2], b: [u8; 2]| a.into_iter().filter(move |&x| !b.contains(&x));
            let yy = sub(s_s.clone(), t_s.clone()).zip(sub(t_s, s_s));
            let zz = xx.chain(yy).map(|x| [x.0, x.1]).flatten().collect::<Vec<u8>>();
            return Ok(zz);
    }
    pub fn query_move(&self) -> Result<Vec<u8>, ()> {
        let piece = |ps: &[Piece; BLOCK_AND_BLACK]| (0..10).into_iter().map(|i|ps[i].one_dim()).collect::<Vec<u8>>().try_into().unwrap();
        let space = |ps: &[Piece; BLOCK_AND_BLACK]| [ps[10].one_dim(), ps[11].one_dim()];
        let ms = self.search();
        if ms.len() >= 2 {
            let state = State::from_u32(ms[1]);
            let source: [u8; 10] = piece(&self.piece);
            let target: [u8; 10] = piece(&state.piece);
            let s_s = space(&self.piece);
            let t_s = space(&state.piece);
            let sub = |a: [u8; 10], b: [u8; 10]| a.into_iter().filter(|&x| !b.contains(&x)).collect::<Vec<u8>>();
            let xx = sub(source.clone(), target.clone()).into_iter().zip(sub(target, source));
            let sub = |a: [u8; 2], b: [u8; 2]| a.into_iter().filter(move |&x| !b.contains(&x));
            let yy = sub(s_s.clone(), t_s.clone()).zip(sub(t_s, s_s));
            let zz = xx.chain(yy).map(|x| [x.0, x.1]).flatten().collect::<Vec<u8>>();
            return Ok(zz);
        }
        Err(())
    }
    fn find_move(&self, who: u8) -> Vec<Move> {
        // 棋子, 提供长宽属性
        let p: Piece = self.piece[who as usize];
        // 棋子当前坐标
        let pos = p.one_dim();

        // 10号空格当前位置坐标
        let space_10 = self.piece[10].one_dim();
        // 11号空格当前位置坐标
        let space_11 = self.piece[11].one_dim();
        let other = |who| if who == space_10 { space_11 } else { space_10 };

        let mut res: Vec<Move> = Vec::<Move>::new();
        for dir in 0..4 {
            match p.need_of_dir(dir) {
                Resource::One(p0) => {
                    // 能动，且只消耗一个空格
                    if space_10 == p0 || space_11 == p0 {
                        let odim = p.one_dim_officer();
                        // 双空相连
                        if (self.horizontal_space() && (p.is_soldier() || p.is_h_officer()))
                            || (self.vertical_space() && (p.is_soldier() || p.is_v_officer()))
                        {
                            if p.is_soldier() {
                                res.push(Move::from_change(pos, space_10));
                                res.push(Move::from_change(pos, space_11));
                            } else {
                                match dir {
                                    0 => {
                                        res.push(Move::a2b_b2c(pos, p0, odim));
                                        res.push(Move::change_ab_c2d(pos, other(who), p0, odim));
                                    }
                                    1 => {
                                        res.push(Move::a2b_b2c(p0, pos, odim));
                                        res.push(Move::change_ab_c2d(pos, p0, other(p0), odim));
                                    }
                                    2 => {
                                        res.push(Move::a2b_b2c(p0, pos, odim));
                                        res.push(Move::change_ab_c2d(pos, p0, other(p0), odim));
                                    }
                                    3 => {
                                        res.push(Move::a2b_b2c(pos, p0, odim));
                                        res.push(Move::change_ab_c2d(other(p0), pos, p0, odim));
                                    }
                                    _ => {}
                                }
                            }
                        } else if p.is_soldier() {
                            res.push(Move::from_change(pos, p0));
                        } else if dir == 0 || dir == 3 {
                            res.push(Move::a2b_b2c(pos, p0, odim));
                        } else {
                            res.push(Move::a2b_b2c(p0, pos, odim))
                        }
                    }
                }
                Resource::Two(pos1, pos2) => {
                    if space_10 == pos1 && space_11 == pos2 {
                        // 能动，且消耗两个空格
                        if let Resource::BossMove(x) = p.boss_move_pos(dir, space_10, space_11) {
                            res.push(Move::from_6u8(x));
                        } else if let Resource::Two(_r0, r1) = p.release_of_dir(dir) {
                            res.push(Move::change_ab_c2d(pos, pos1, pos2, r1));
                        }
                    }
                }
                _ => continue,
            }
        }
        res
    }
    pub fn search(&self) -> Vec<u32> {
        let mut history = BTreeMap::<u32, u32>::new();
        history.insert(self.zip(), 0);
        let mut queue = VecDeque::<u32>::new();
        queue.push_back(self.zip());
        while queue.len() > 0 {
            let pre = queue.pop_front().unwrap();
            let state = State::from_u32(pre);
            for m in state.next_steps() {
                let mut next: State = state.clone();
                let over = next.apply_move(m);
                let z = next.zip();
                if !history.contains_key(&z) {
                    history.insert(z, pre);
                    queue.push_back(z);
                    if over {
                        return Self::pick(z, &history);
                    };
                }
            }
        }
        vec![]
    }
    fn pick(from: u32, his: &BTreeMap<u32, u32>) -> Vec<u32> {
        let mut key = from;
        let mut steps = Vec::new();
        while key > 0 {
            steps.push(key);
            key = his[&key];
        }
        return steps.into_iter().rev().collect();
    }
}

fn u32_to_pieces(zip: u32) -> Vec<Piece> {
    // 空格所在压缩位序
    let space = (|ss| [ss >> 4, ss & 0xf])((zip >> (BLOCK_AND_BLACK * BLOCK_BITS)) as u8);
    // 使用坐标和类型创建一个Piece
    let make_piece = |x, y, t: u8| Piece::new((t >> 1) + 1, (t & 1) + 1, x, y);
    // 空格块
    let mut s_p: Vec<Piece> = Vec::new();
    // 非空块
    let mut o_p: Vec<Piece> = Vec::new();
    // 空位x坐标
    let mut x_idx: u8 = 0;
    // 空位y坐标
    let mut y_idx: u8 = 0;
    // 棋盘已填充列高度
    let mut col: [u8; BOARD_WIDTH as usize] = Default::default();
    for i in 0..BLOCK_AND_BLACK {
        let p = make_piece(x_idx, y_idx, ((zip >> (i * BLOCK_BITS)) & BLOCK_MASK) as u8);
        if space.contains(&(i as u8)) {
            s_p.push(p);
        } else {
            o_p.push(p);
        }
        // 按棋子宽度，更新棋盘已填充列高度
        for j in 0..p.w {
            col[(x_idx + j) as usize] = y_idx + p.h;
        }
        // 查找下一个空位
        while col[x_idx as usize] > y_idx {
            x_idx += 1;
            // 行尾，下一行
            if x_idx >= BOARD_WIDTH {
                x_idx = 0;
                y_idx += 1;
            }
        }
    }
    o_p.extend(s_p);
    o_p
}

impl Piece {
    fn new(w: u8, h: u8, x: u8, y: u8) -> Piece {
        Piece { w, h, x, y }
    }
    fn is_soldier(&self) -> bool {
        self.w == 1 && self.h == 1
    }

    fn is_h_officer(&self) -> bool {
        self.w == 2 && self.h == 1
    }

    fn is_v_officer(&self) -> bool {
        self.w == 1 && self.h == 2
    }

    fn is_over(&self) -> bool {
        self.w == 2 && self.h == 2 && self.x == 1 && self.y == 3
    }

    fn move_to(&self, pos: u8) -> Piece {
        Piece {
            w: self.w,
            h: self.h,
            x: pos % BOARD_WIDTH,
            y: pos / BOARD_WIDTH,
        }
    }

    fn boss_move_pos(&self, dir: u8, s1: u8, s2: u8) -> Resource {
        if self.w == 2 && self.h == 2 {
            let p = self.one_dim();
            let d: u8 = p + BOARD_WIDTH;
            let r = p + 1;
            let f = d + 1;
            match dir {
                0 => Resource::BossMove([p, s1, s1, d, s2, f]),
                1 => Resource::BossMove([p, r, s1, p, s2, d]),
                2 => Resource::BossMove([p, d, s1, p, s2, r]),
                3 => Resource::BossMove([p, s1, s1, r, s2, f]),
                _ => Resource::None,
            }
        } else {
            Resource::None
        }
    }

    // 移动需要的位置
    fn need_of_dir(&self, dir: u8) -> Resource {
        if match dir {
            0 => self.y == 0,
            1 => self.x + self.w == BOARD_WIDTH,
            2 => self.y + self.h == BOARD_HIGHT,
            3 => self.x == 0,
            _ => false,
        } {
            return Resource::None;
        }
        match dir {
            0 => Resource::h(self.w, self.x + (self.y - 1) * BOARD_WIDTH),
            1 => Resource::v(self.h, self.x + self.y * BOARD_WIDTH + self.w),
            2 => Resource::h(self.w, self.x + (self.y + self.h) * BOARD_WIDTH),
            3 => Resource::v(self.h, self.x + self.y * BOARD_WIDTH - 1),
            _ => Resource::None,
        }
    }

    // 移动后释放的位置
    fn release_of_dir(&self, dir: u8) -> Resource {
        match dir {
            0 => Resource::h(self.w, self.x + (self.y + self.h - 1) * BOARD_WIDTH),
            1 => Resource::v(self.h, self.one_dim()),
            2 => Resource::h(self.w, self.one_dim()),
            3 => Resource::v(self.h, self.x + self.w + self.y * BOARD_WIDTH - 1),
            _ => Resource::None,
        }
    }

    // 武将副格一维坐标
    fn one_dim_officer(&self) -> u8 {
        self.x + self.w - 1 + (self.y + self.h - 1) * BOARD_WIDTH
    }

    // 主格一维坐标
    fn one_dim(&self) -> u8 {
        self.x + self.y * BOARD_WIDTH
    }

    fn zip(&self) -> u32 {
        (((self.w - 1) << 1) | (self.h - 1)) as u32
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_from_u32() {
        let zip = get_init_zip();
        let state = State::from_u32(zip);
        assert_eq!(state.horizontal_space(), true);
        assert_eq!(state.vertical_space(), false);
    }

    fn get_init_zip() -> u32 {
        let mut zip: u32 = (9 << 4) | 10;
        [0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 3, 1].map(|x| zip = zip << 2 | x);
        zip
    }

    #[test]
    fn test_zip() {
        let zip = get_init_zip();
        let state = State::from_u32(zip);
        assert_eq!(state.zip(), zip);
    }

    #[test]
    fn test_find_move() {
        let zip: u32 = get_init_zip();
        let state = State::from_u32(zip);
        for i in 0..10 {
            let moves = state.find_move(i);
            assert_eq!(moves.len(), if i < 6 { 0 } else { 2 });
        }
    }

    #[test]
    fn test_move_to() {
        let p = Piece::new(2, 1, 1, 2);
        let p1 = p.move_to(10);
        assert_eq!(p1.x, 2);
        assert_eq!(p1.y, 2);
        let mut state = State::from_u32(get_init_zip());
        state.apply_move(Move::from_change(16, 17));
    }

    #[test]
    fn test_piece_officer() {
        let p: Piece = Piece::new(2, 1, 1, 2);
        assert_eq!(p.is_soldier(), false);
        assert_eq!(p.is_h_officer(), true);
        assert_eq!(p.is_v_officer(), false);
        assert_eq!(p.one_dim(), 9);
        assert_eq!(p.one_dim_officer(), 10);
        if let Resource::Two(p0, p1) = p.need_of_dir(0) {
            assert_eq!(p0, 5);
            assert_eq!(p1, 6);
        } else {
            assert_eq!(false, true);
        }
        if let Resource::One(p0) = p.need_of_dir(1) {
            assert_eq!(p0, 11);
        } else {
            assert_eq!(false, true);
        }
        if let Resource::Two(p0, p1) = p.need_of_dir(2) {
            assert_eq!(p0, 13);
            assert_eq!(p1, 14);
        } else {
            assert_eq!(false, true);
        }
        if let Resource::One(p0) = p.need_of_dir(3) {
            assert_eq!(p0, 8);
        } else {
            assert_eq!(false, true);
        }
    }
}
